import java.util.Scanner;

/**
 * @author vivi
 * @description
 * @date 2024/5/14
 */
public class demo1 {
    public static void main (String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();

        int ret = n;
        for(int i = 0; i < m - 1; i++)
        {
            ret = ret * (n - 1) % 109;
        }

        System.out.println(ret);

    }
}
